#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define TYPE int

typedef struct Node
{
	struct Node* prev;	// 前一个元素
	TYPE data;			// 数据
	struct Node* next;	//后一个元素
}Node;

Node* create_node(TYPE data)
{
	Node* node = malloc(sizeof(Node));
	node->prev = NULL;
	node->data = data;
	node->next = NULL;
	return node;
}

typedef struct List
{
	Node* head;
	Node* tail;
	size_t size;
}List;

// 创建
List* create_list(void);
// 销毁
void destory_list(List* list);
// 头加
void head_add_list(List* list,TYPE data);
// 尾加
void tail_add_list(List* list,TYPE data);
// 插入
bool insert_list(List* list,int index,TYPE data);
// 删除头
bool del_head_list(List* list);
// 删除尾
bool del_tail_list(List* list);
// 按位置删除
bool delete_index(List* list,int index);
// 值删除
bool delete_value_list(List* list,TYPE data);
// 遍历
void show_list(List* list);
// 排序
void sort_list(List* list);

int main()
{
	List* list = create_list();
	for(int i=0; i<10; i++)
	{
		head_add_list(list,i);
	}
	for(int i=14; i<19; i++)
	{
		tail_add_list(list,i);
	}
	show_list(list);
	insert_list(list,6,666);
	show_list(list);
	printf("按照位置删除后:\n");
	delete_index(list,5);
	show_list(list);
	printf("---------\n");
	delete_value_list(list,17);
	show_list(list);
	printf("---------\n");
//	sort_list(list);
	show_list(list);
	destory_list(list);
}

// 创建
List* create_list(void)
{
	List* list = malloc(sizeof(List));
	list->head = NULL;
	list->tail = NULL;
	list->size = 0;
	return list;
}
// 销毁
void destory_list(List* list)
{
	while(del_head_list(list));
	//free(list->head);
	//free(list->tail);
	free(list);
}
// 头加
void head_add_list(List* list,TYPE data)
{
	Node* node = create_node(data);
	if(0 == list->size)
	{
		list->head = node;
		list->tail = node;
	}
	else
	{
		node->next = list->head;
		list->head->prev = node;
		list->head = node;
	}
	list->size++;

}
// 尾加
void tail_add_list(List* list,TYPE data)
{
	Node* node = create_node(data);
	if(0 == list->size)
	{
		list->head = node;
		list->tail = node;
	}
	else
	{
		list->tail->next = node;
		node->prev = list->tail;
		list->tail = node;
	}
	list->size++;
}
// 插入
bool insert_list(List* list,int index,TYPE data)
{
	if(index >= list->size || index < 0) return false;
	Node* in = create_node(data);
	Node* node = list->head;
	for(int i=0; i<index; i++)
	{
		if(index < list->size/2) node = node->next;
		else
		{
			node = list->tail;
			node = node->prev;
		}
	}
	if(index == 0)
	{
		head_add_list(list,data);
		return true;
/*
		in->next = node;
		node->prev = in;
		list->head = in;
		list->size++;
		return true;
*/
	}
	Node* left = node->prev;
	left->next = in;
	in->prev = left;
	in->next = node;
	node->prev = in;
	list->size++;
	return true;
}

// 删除头
bool del_head_list(List* list)
{
	if(list->size <= 0) return false;
	Node* node = list->head;
	if(1 == list->size)
	{
		list->head = NULL;
		list->tail = NULL;
	}
	else
	{
		list->head = node->next;
		node->next->prev = NULL;
	}
	free(node);
	list->size--;
	return true;
}
// 删除尾
bool del_tail_list(List* list)
{
	if(list->size <= 0) return false;
	Node* node = list->tail;
	if(1 == list->size)
	{
		list->head = NULL;
		list->tail = NULL;
	}
	else
	{
		list->tail = node->prev;
		node->prev->next = NULL;
	}
	free(node);
	list->size--;
	return true;
}

// 按位置删除
bool delete_index(List* list,int index)
{
	if(list->size <= 0 || index < 0 || index >= list->size) return false;
	if(0 == index) del_head_list(list);
	if(list->size-1 == index) del_tail_list(list);
	Node* node = list->head;
	for(int i=0; i<index; i++)
	{
		if(index < list->size/2) node = node->next;
		else
		{
			node = list->tail;
			node = node->prev;
		}
	}
	if(index != 0) node->prev->next = node->next;
	else list->head = node->next;
	if(index != list->size-1) node->next->prev = node->prev;
	else list->tail = node->prev;
	free(node);
	list->size--;
	return true;
}
// 值删除
bool delete_value_list(List* list,TYPE data)
{
	if(list->size <= 0) return false;
	if(data == list->head->data) return del_head_list(list);
	if(data == list->tail->data) return del_tail_list(list);
	Node* node = list->head;
	/*while(NULL != node)
	{
		if(node->data == data) break;
		node = node->next;
	}
	node->prev->next = node->next;
	node->next->prev = node->prev;
	free(node);*/
	for(int i=0; i<list->size; i++)
	{
		if(node->data == data)
			delete_index(list,i);
		node = node->next;
	}
	list->size--;
	return false;
}
// 遍历
void show_list(List* list)
{
	printf("正序：");
	for(Node* i=list->head; i!=NULL; i=i->next)
	{
		printf("%d ",i->data);
	}
	printf("\n逆序：");
	for(Node* i=list->tail; i!=NULL; i=i->prev)
	{
		printf("%d ",i->data);
	}
	printf("\n");
}

// 排序
void sort_list(List* list)
{
	/*
	for(Node* i=list->head->next; i->next!=list->tail; i=i->next)
	{
		for(Node* j=i->next; j->next!=NULL; j=j->next)
		{
			if(i->data > j->data)
			{
				i->prev->next = j;
				j->prev = i->prev;
				j->next->prev = i;
				i->next = j->next;
				j->next = i;
				i->prev = j;
			}
		}
	}
	*/
}
